package com.nanbei.sort;

import java.util.Arrays;

/**
 * @ClassDescription: 归并加插入排序
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/6/27 17:44
 */
public class MergeAndInsertion {

    public static void main(String[] args) {
        int[] insertion = sort(new int[]{9,10,6,3,7,4,5,8,1,2,11});
        System.out.println(Arrays.toString(insertion));
    }

    public static int[] sort(int[] nums) {
        int[] ints = new int[nums.length];
        split(nums, 0, nums.length - 1, ints);
        return nums;
    }

    /**
     * - 分 - 每次从中间切一刀，处理的数据少一半
     * - 治 - 当数据仅剩一个时可以认为有序
     * - 合 - 两个有序的结果，可以进行合并排序
     * @param nums 待排序数组
     * @param left 待排序数组的左边界
     * @param right 待排序数组的右边界
     * @param ints 临时数组（用来合并有序数组）
     */
    public static void split(int[] nums, int left, int right, int[] ints) {


        if (right - left <=64) {
            insertion(nums, left, right);
            return;
        }
        int mid = (left + right) >> 1;
        split(nums, left, mid, ints);
        split(nums, mid + 1, right, ints);

        merge(nums,left,mid,mid+1,right,ints);
        System.arraycopy(ints,0,nums,left,right-left+1);
    }

    /**
     *
     * @param nums  原始数组
     * @param left  第一个有序数组开始的下标
     * @param leftEnd  第一个有序数组结束的下标
     * @param right 第二个有序数组开始的下标
     * @param rightEnd 第二个有序数组结束的下标
     * @param ints 临时数组
     */
    private static void merge(int[] nums, int left, int leftEnd, int right, int rightEnd, int[] ints) {
        int index = 0;
        while (left <= leftEnd && right <= rightEnd){
            int leftNum = nums[left];
            int rightNum = nums[right];
            if (leftNum < rightNum){
                ints[index++] =leftNum;
                left++;
            }else {
                ints[index++] = rightNum;
                right++;
            }
        }
        if (left <= leftEnd){
            while (left <= leftEnd){
                ints[index++] = nums[left++];
            }
        }
        if (right <= rightEnd){
            while (right <= rightEnd){
                ints[index++] = nums[right++];
            }
        }
    }

    public static void insertion(int[] nums,int left,int right){
        for (int low = left+1; low < right+1 ; low++) {
            int temp = nums[low];
            int i = low-1;
            // 未找到插入位置，将较大的元素依次向后插入一位
            while ( i >= left && temp < nums[i]){
                nums[i+1] = nums[i--];
            }
            // 找到插入位置
            if (i != low-1){
                nums[i+1] = temp;
            }
        }
    }


}
